A Parallel Genetic Algorithm for Three Dimensional Bin Packing with Heterogeneous Bins

摘要

This paper presents a parallel genetic algorithm for three dimensional binpacking with heterogeneous bins using Hadoop Map-Reduce framework. The mostcommon three dimensional bin packing problem which packs given set of boxesinto minimum number of equal sized bins is proven to be NP Hard. The variationof three dimensional bin packing problem that allows heterogeneous bin sizesand rotation of boxes is computationally more harder than common threedimensional bin packing problem. The proposed Map-Reduce implementation helpsto run the genetic algorithm for three dimensional bin packing withheterogeneous bins on multiple machines parallely and computes the solution inrelatively short time.